import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BinaryTree {
    static class Treenode{
        public char val;
        public  Treenode left;
        public  Treenode right;

        public Treenode(char val) {
            this.val = val;
        }
    }

    //根节点
    public Treenode createnode(){
        Treenode A=new Treenode('A');
        Treenode B=new Treenode('B');
        Treenode C=new Treenode('C');
        Treenode D=new Treenode('D');
        Treenode E=new Treenode('E');
        Treenode F=new Treenode('F');
        Treenode G=new Treenode('G');
        Treenode H=new Treenode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;
        return A;

    }
    //前序遍历
    public void preorder(Treenode root){
        if(root==null) return;
        System.out.println(root.val+" ");
        preorder(root.left);
        preorder(root.right);

    }
    //中序遍历
    public  void inorder(Treenode root){
        if(root==null){
            return;
        }
        inorder(root.left);
        System.out.println(root.val+" ");
        inorder(root.right);
    }
    public  void PostOrder(Treenode root){
        if(root==null){
            return;
        }
        preorder(root.left);
        preorder(root.right);
        System.out.println(root.val+" ");

    }
    List<Treenode> list=new ArrayList<>();
    public Treenode preorder1(Treenode root){

        if (root==null)return (Treenode) list;
        list.add(root);
        preorder1(root.left);
        preorder1(root.right);
        return (Treenode) list;


    }
    public Treenode preorder3(Treenode root){
        List<Treenode> list1=new ArrayList<Treenode>();
        if(root==null)
            return (Treenode) list1;
        List<Treenode> left1= (List<Treenode>) preorder3(root.left);
        list1.addAll(left1);
        List<Treenode> right1= (List<Treenode>) preorder3(root.right);
        list1.addAll(right1);
        return (Treenode) list1;


    }
    int size=0;
    public void sizeth(Treenode root){
        if(root==null){
            return ;

        }
        size++;
        List<Treenode> lefttree= (List<Treenode>) preorder3(root.left);
        List<Treenode> righttree= (List<Treenode>) preorder3(root.right);



    }
    public int size2(Treenode root){
        if(root==null)return 0;
        return 1+size2(root.left)+size2(root.right);
    }
   /* /获取叶子节点个数*/
    int sizeleaf=0;

    public void getleafSize(Treenode root){
        if(root.left==null && root.right==null){
            return ;

        }
        sizeleaf++;
        getleafSize(root.left);
        getleafSize(root.right);




    }
    //通过递归
    int size1=0;
    public int getSizeleaf1(Treenode root){
        if(root==null)return 0;
        if(root.left==null && root.right==null){
            return 1;
        }

        return getSizeleaf1(root.left)+getSizeleaf1(root.right);


    }
    //第k层有几个节点
    public int geleavefsize(Treenode root,int k){
        if (root==null)return 0;
        if(k==1)return  1;
        return geleavefsize(root.left,k-1)+geleavefsize(root.right,k-1);
    }
    int result=0;
    public int getheight(Treenode root){
        if (root==null)return 0;

        result=getMax(getheight(root.left)+1,getheight(root.right)+1);
        return result;

    }
    public static int getMax(int num1, int num2) {
        return num1 > num2? num1 : num2;




    }
    public boolean find(Treenode root,char key){
        if(root==null){
            return  false;
        }
        if(root.val==key){
            return true;
        }
        boolean leftfind=find(root.left,key);
        if(leftfind==true)return true;
        boolean rightfind=find(root.right,key);
        if(rightfind==true)return true;
        return false;

    }
   


















    }

